package com.strutor.likou.lstack;
import org.omg.CORBA.Object;

import java.util.LinkedList;

/**
 * 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * push(x) -- 将元素 x 推入栈中。
 * pop() -- 删除栈顶的元素。
 * top() -- 获取栈顶元素。
 * getMin() -- 检索栈中的最小元素。
 *
 * */
public class MinStack<E extends Comparable<E>> {
//    private E [] data;
//    private int size;
//
//    public MinStack(int capacity){
//        data = (E[])new Object[capacity];
//        size = 0;
//    }
//
//    public MinStack(){
//        this(10);
//    }
//
//    public int getSize() {
//        return size;
//    }
//
//    public void push(E e){
//        data[size]=e;
//        size++;
//    }
//
//    public E pop(){
//        E del = data[size-1];
//        data[size-1] = null;
//        size--;
//        return del;
//    }
//
//    public E top(){
//        return data[size-1];
//    }
//
//    public E getMin(){
//        E e = data[0];
//        for (int i = 1; i < size; i++) {
//            if (e.compareTo(data[i])>=0){
//                e = data[i];
//            }
//        }
//        return e;
//    }
    private int [] data;
    private int size;

    public MinStack(int capacity){
        data = new int[capacity];
        size = 0;
    }

    public MinStack(){
        this(10);
    }

    public int getSize() {
        return size;
    }

    public void push(int e){
        if (size>=data.length){
            resize(data.length*2);
        }
        data[size] = e;
        size ++;
    }

    public void resize(int capacity){
        int [] newData = new int[capacity];
        for (int i = 0; i < data.length; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    public int pop(){
        if (data.length < data.length/2){
            resize(data.length/2);
        }
        int del = data[size-1];
        data[size-1] = 0;
        size--;
        return del;
    }

    public int top(){
        return data[size-1];
    }

    public int getMin(){
        int e = data[0];
        for (int i = 1; i < size; i++) {
            if (e > data[i]){
                e = data[i];
            }
        }
        return e;
    }
}


